package Other.DP;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author:gao
 * @date:2020/7/11
 * @time:13:32
 * @version:0.0.1
 * @description:none
 */

public class MinimumTotal {

    public static void main(String[] args) {
//        Solution solution = new Solution();
//        List<List<Integer>> ls = new ArrayList<>();
//        List<Integer> list =new ArrayList<>();
//        list.add(2);
//        ls.add(list);
//        list = new ArrayList<>();
//        list.add(3);
//        list.add(4);
//        ls.add(list);
//        list = new ArrayList<>();
//        list.add(6);
//        list.add(5);
//        list.add(7);
//        ls.add(list);
//        list = new ArrayList<>();
//        list.add(4);
//        list.add(1);
//        list.add(8);
//        list.add(3);
//        ls.add(list);
//        solution.minimumTotal(ls);
    }
}

class Solution8854 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int row = triangle.size();
        if (row ==0) return 0;
        if (row==1) return triangle.get(0).get(0);
        List<Integer> dpList0 = new ArrayList<>();
        List<Integer> dpList1 = new ArrayList<>();
        int ans = Integer.MAX_VALUE;
        dpList0.add(triangle.get(0).get(0));
        List<Integer> lastList = null;
        List<Integer> curList = null;
        for (int i = 1; i < row ; i++) {
            if(i%2!=0){
                lastList = dpList0;
                curList = dpList1;
            }else{
                lastList = dpList1;
                curList = dpList0;
            }
            curList.clear();
            for (int j = 0; j <triangle.get(i).size() ; j++) {
                if (j==0){
                    curList.add(lastList.get(0)+triangle.get(i).get(0));
                }else if (j>=lastList.size()){
                    curList.add(lastList.get(j-1)+triangle.get(i).get(j));
                }
                else{
                    int lastMin = Math.min(lastList.get(j),lastList.get(j-1));
                    curList.add(triangle.get(i).get(j)+lastMin);
                }
            }
        }
        for (Integer i : curList){
            if(i<ans)ans=i;
        }
        return ans;
    }
}
